package com.example.leetcode.DFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 题目描述
 * 给定一个二维的非负整数矩阵，每个位置的值表示海拔高度。假设左边和上边是太平洋，右
 * 边和下边是大西洋，求从哪些位置向下流水，可以流到太平洋和大西洋。水只能从海拔高的位置
 * 流到海拔低或相同的位置。
 * 输入输出样例
 * 输入是一个二维的非负整数数组，表示海拔高度。输出是一个二维的数组，其中第二个维度
 * 大小固定为 2，表示满足条件的位置坐标。
 * Input:
 * 太平洋 ~ ~ ~ ~ ~
 * ~ 1 2 2 3 (5) *
 * ~ 3 2 3 (4) (4) *
 * ~ 2 4 (5) 3 1 *
 * ~ (6) (7) 1 4 5 *
 * ~ (5) 1 1 2 4 *
 * * * * * * 大西洋
 * Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
 * 在这个样例中，有括号的区域为满足条件的位置
 *
 * @ClassName Solution_417
 * @Description TODO
 * @Author liuzhihui
 * @Date 6/5/2021 下午 8:08
 * @Version 1.0
 **/
public class Solution_3_417 {
    //控制水流的方向
    private int[][] diretions =new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();

        if (heights.length == 0){
            return result;
        }

        // 二维数组竖边
        int n = heights.length;
        // 二维数组横边
        int m = heights[0].length;

        // 记录水流能流到太平洋的大陆单元格
        boolean[][] qo =new boolean[n][m];
        // 记录水流能流到大西洋的大陆单元格
        boolean[][] ao =new boolean[n][m];

        //对横边遍历
        for (int i = 0; i < m; i++) {
            // 上边界找水流能流到太平洋的大陆单元格
            dfs(heights, 0, i, qo);
            // 下边界找水流能流到大西洋的大陆单元格
            dfs(heights, n - 1,i , ao);
        }
        // 竖边遍历
        for (int i = 0; i < n; i++) {
            // 左边界找水流能流到太平洋的大陆单元格
            dfs(heights, i, 0, qo);
            // 下边界找水流能流到大西洋的大陆单元格
            dfs(heights,i ,m-1,ao);
        }
        //遍历二维数组
        //竖边
        for (int i = 0; i < n; i++) {
            //横边
            for (int j = 0; j < m; j++) {
                //水流能流到太平洋的大陆单元格 与 水流能流到大西洋的大陆单元格
                //它们的交集就是要找的单元格，即流向太平洋又流向大西洋
                if (qo[i][j] && ao[i][j]){
                    result.add(Arrays.asList(i,j));
                }
            }
        }
        return result;
    }

    private void dfs(int[][] heights, int x, int y, boolean[][] can_Float) {
        //设置当前单元格为水，流过
        can_Float[x][y] = true;
        // 从当前单元格的四个方向找
        for (int i = 0; i < 4; i++) {
            int new_x = x + diretions[i][0];
            int new_y= y + diretions[i][1];
            //in_Island判断单元格是否在岛上
            //heights[x][y] > heights[new_x][new_y] 判断递增
            //can_Float[new_x][new_y] 判断当前单元格水是否流过
            if (!in_Island(new_x, new_y,heights) || heights[x][y] > heights[new_x][new_y] || can_Float[new_x][new_y]){
                continue;
            }
            dfs(heights,new_x,new_y,can_Float);
        }
    }
    private boolean in_Island(int x, int y ,int[][] matrix){
        return (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length);
    }
}
